// 2025/11/12
// LRU缓存

class LRUCache {
    struct ListNode
    {
        ListNode(int key = -1, int val = -1) : _key(key), _val(val) {}
        int _key, _val;
        ListNode* next = this;
        ListNode* prev = this;
    };
    void moveToHead(ListNode* cur)
    {
        // 删掉目标结点
        ListNode* prev = cur->prev, * next = cur->next;
        if (prev != cur) prev->next = next;
        if (next != cur) next->prev = prev;

        // 插入头部
        _head.next->prev = cur;
        cur->next = _head.next;
        _head.next = cur;
        cur->prev = &_head;
    }
public:
    LRUCache(int capacity)
        : _capacity(capacity)
    {
    }

    int get(int key) {
        auto it = _mp.find(key);
        if (it != _mp.end())
        {
            ListNode* cur = it->second;
            moveToHead(cur);
            return cur->_val;
        }
        return -1;
    }

    void put(int key, int value) {
        auto it = _mp.find(key);
        if (it != _mp.end())
        {
            ListNode* cur = it->second;
            moveToHead(cur);
            cur->_val = value;
        }
        else
        {
            ListNode* cur = new ListNode(key, value);
            moveToHead(cur);
            _mp[key] = cur;
            if (_mp.size() > _capacity)
            {
                // 删掉尾结点
                ListNode* tail = _head.prev;
                tail->prev->next = &_head;
                _head.prev = tail->prev;
                _mp.erase(tail->_key);
                delete tail;
            }
        }
    }

    int _capacity;
    ListNode _head;
    unordered_map<int, ListNode*> _mp;
};